#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>


// FUNCTION: 定义动态数组
typedef int ElemType;

typedef struct {
	ElemType *elem;//存储元素的起始地址
	int TableLen;//元素个数
} SSTable;


// FUNCTION: 随机数生成
void ST_Init(SSTable &ST, int len) {
	// NOTE: 变量初始化
	// STEP: 确定表长
	ST.TableLen = len;

	// STEP: 申请动态数组实际空间
	ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);

	// STEP: 存放赋值变量是的索引
	int i;


	// NOTE: 生成随机数
	srand(time(NULL));


	// NOTE: 将数据存储到数组中
	// HINT: 为啥这里零号位置也存放了随机了数据？是为折半查找服务的。
	for (i = 0; i < ST.TableLen; i++) {
		ST.elem[i] = rand() % 100;
	}
}


// FUNCTION: 输出数组中全部元素
void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}

	printf("\n");
}


// FUNCTION: 实现交换
void swap(ElemType &a, ElemType &b) {
	ElemType tmp;
	tmp = a;
	a = b;
	b = tmp;
}


// FUNCTION: （挖坑法）实现分割。比64小的放在左边，比64大的放在右边
// REVIEW: 以最左边的元素作为分界值，并用临时变量pivot存储起来。于是，分界值所对应的数组元素，就可看成是多余的。然后，通过左右指针low和high，逐步向数组中间逼近。先high向low逼近，将比分界值小的数填补到low的位置上。接着low向high逼近，将比分界值大的数填补到high的位置上……反复重复上述操作。直到low < high。所以，上述操作很形象得被称为：“挖坑法”。
// 原始数据：64 94 95 79 69 84 18 22 12 78
int Partition_wangdao(ElemType A[], int low, int high) {
	// NOTE: 将拟定的分界值暂存（此时认为low所指元素是坑位）
	ElemType pivot = A[low];


	// NOTE: 循环终点
	while (low < high) {
		// STEP: 将high从后往前遍历数组，找到比分界值小的数组元素索引
		while (low < high && A[high] >= pivot)
			--high;

		// STEP: 把该比分界值小的元素放置到坑位（同时，角色互换，此时认为high所指元素是坑位）
		A[low] = A[high];

		// STEP: 将low从后往前遍历数组，找到比分界值大的数组元素索引
		while (low < high && A[low] <= pivot)
			++low;

		// STEP: 把该比分界值大的该元素放置到坑位（同时，角色互换，此时认为high所指元素是坑位）
		A[high] = A[low];
	}


	// NOTE: 将分界值放回数组中
	A[low] = pivot;


	// NOTE: 返回分界点的索引值
	return low;
}


// FUNCTION: （交换法）实现分割。即：快速找出数据的分界值，让分界值左边的元素均小，右边的元素均大。
// 原始数据：64 94 95 79 69 84 18 22 12 78
// REVIEW: （后续提及的字母都表示索引，除非有另外说明）开始执行时，我们姑且认为分界值的数值与right所对应的数组元素相同，且假设会出现在k处，k = left。我们另外定义一个i用于遍历数组，初值记i = left。每一次i对应元素与right对应元素比较大小。如果小于，则交换i和k的对应元素，并++k，i再往后挪一个。如此往复，直到i增加到right为止，就是i在增加过程中，必须保证i < right。
int Partition(int *arr, int left, int right) {
	// NOTE: 变量声明
	// REVIEW: i和k都是索引值。其中，i用于遍历数组全部元素；k用于记录比分界值小的元素下标。经过循环后，k就是分界点的索引。
	int k, i;


	// NOTE: 进行循环，寻找分界点
	// REVIEW: 我们假设分界点是位于最后边的数组元素。寻找分界点的过程中，可以看做是一个粗分类的过程。故能够保证分界点一定比左边元素大，比右边元素小。
	for (k = i = left; i < right; i++) {
		// 判断索引为i的元素值，是否比索引为right的小？如果成立！则交换索引值为i和k的元素值。
		// REVIEW: 这样就能够保证，k之前的所有元素值都比当前区域中的最右边元素小。故，当遍历完成后，必能够实现分类。
		if (arr[i] < arr[right]) {
			// 实现两数交换
			swap(arr[i], arr[k]);

			// 分界点的索引就要往后推一格
			// REVIEW: 因为我们假设分界点是在当前区域的低于个元素。但经比较后，较小的数值会往前站。于是乎，分界点就被迫往后推。故，分界点的出现位置只需要自增1即可。
			++k;
		}
	}


	// NOTE: 将分界点放在正确的位置上
	swap(arr[k], arr[right]);


	// NOTE: 返回分界点的索引值
	return k;
}


// FUNCTION: 递归实现快速排序
void QuickSort(ElemType A[], int low, int high) {
	// STEP: 判断是否为递归出口
	if (low < high) {
		// STEP: 获取分界点索引值。
		// HINT: 分界点左边的元素都比分割点要小，右边的元素比分割点大。
		// int pivot_index = Partition(A, low, high);
		int pivot_index = Partition_wangdao(A, low, high);

		// STEP: 递归实现左半区的排序。
		QuickSort(A, low, pivot_index - 1);

		// STEP: 递归实现右半区的排序。
		QuickSort(A, pivot_index + 1, high);
	}
}


int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	// STEP: 声明动态数组
	SSTable ST;

	// STEP: 声明一组数
	ElemType A[10] = {64, 94, 95, 79, 69, 84, 18, 22, 12, 78};


	// NOTE: 数组元素赋值
	ST_Init(ST, 10);

	// STEP: 数组元素重新赋值（方便填充）
	// REVIEW: 此段代码目的是：在ST_Init执行结束后，ST虽已经初始化，但其中的数据都是随机数，不方便检查程序是否有bug。为了欲使检查变得方便，使用memcpy将自己定义的数组A直接覆盖ST的elem区域。
	// HINT: 内存copy接口。当你copy整型数组，或者浮点型时，要用memcpy。
	// ALERT: 注意区分memcpy和strcpy的区别。
	memcpy(ST.elem, A, sizeof(A));

	printf("Original sequence is: ");
	ST_print(ST);


	// NOTE: 快速排序
	QuickSort(ST.elem, 0, 9);
	printf("After sorting, sequence is: ");
	ST_print(ST);


	return 0;
}